import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.LinkedList;




public class PertNetwork {
	GenericGraph graph;
	
	
	public PertNetwork(){
		graph = new GenericGraph();
	}
	

	// time of every vertex without predecessors = 0
	// if every predecessor of X has had it's earliest time added
		// then the earliest time for vertex X = max of every predecessor of X 
		// max X =( earliest time of predecessor + weight of edge to X )
	public void earliestTimes(LinkedList<String> sortedList){
		for (String s : sortedList){
			Vertex v = graph.getVertex(s);
			// earliest time of the root node is 0
			if (v.getIncomingEdges().isEmpty()){
				v.setEearliestTime(0);
			} else {
				v.setEearliestTime(calculateEarliestTime(v));
			}
		}
	}
	
	public double calculateEarliestTime(Vertex vertex){
		double max = -Double.MAX_VALUE;
		for (Edge e : vertex.getIncomingEdges()){
			if (e.getStart().getEarliestTime() +  e.getStart().getCostToNeighbour(vertex) > max){
				max = e.getStart().getEarliestTime() +  e.getStart().getCostToNeighbour(vertex) ;
			}
		}
		return max;
	}
	
	
	
	// for every vertex without successors the last time = the earliest time
	// if every successor of X has a last time then
		// last time of vertex X = min of all succesors of X
		// min successors of X = (last time successor x - weight of side
		// between successor x and x )

	public void lastTimes(LinkedList<String> sortedList){
		// reverse the list so you start with the last node
		Collections.reverse(sortedList);
		
		for (String s : sortedList){
			Vertex v = graph.getVertex(s);
			// if it's the last node
			if (v.getOutgoingEdges().isEmpty()){
				v.setLastTime(v.getEarliestTime());
			} else {
				v.setLastTime(calculateMinLastTime(v));
			}
		}
	}
	
	public double calculateMinLastTime(Vertex vertex){
		double min = Double.MAX_VALUE;
		for (Edge e : vertex.getOutgoingEdges()){
			if (e.getDestination().getLastTime() - vertex.getCostToNeighbour(e.getDestination()) < min ){
				min = e.getDestination().getLastTime() - vertex.getCostToNeighbour(e.getDestination());
			}
		}
		return min;
	}
	
	
	public LinkedList<String> topologicalSort(){
		LinkedList<String> sortedList = new LinkedList<String>(); 
		
		while (hasUncheckedEdges()){
			for (String s : graph.getVertices().keySet()){
				Vertex tmpVertex = graph.getVertex(s);
				if (!tmpVertex.hasPredecessors() && !tmpVertex.vertexPassed()){
					sortedList.add(tmpVertex.getName());
					tmpVertex.setVertexPassed();
					tmpVertex.setVertexPassed();
				}
			}
		}
		// reset the isPassed booleans in the vertices of the graph
		resetPassed();
		
		return sortedList;
	}
	
	public void resetPassed(){
		for (String s : graph.getVertices().keySet()){
			Vertex v = graph.getVertex(s);
			v.resetVertexPassed();
		}
	}
	
	private boolean hasUncheckedEdges(){
		for (String s : graph.getVertices().keySet()){
			Vertex tmpVertex = graph.getVertex(s);
			if (!tmpVertex.vertexPassed()){
				return true;
			}
		}
		return false;
	}
	
	

	/**
	 * Test method that populates the graph, set earliest and last times,
	 * and then prints a textual representation of the graph
	 */
	public LinkedHashMap<String, Vertex> testGraph(){
		LinkedList<String> sortedList = topologicalSort();
		earliestTimes(sortedList);
		lastTimes(sortedList);
		
		return (LinkedHashMap<String, Vertex>) graph.getVertices();
	}
	
	/**
	 * Prints a textual representation of the graph
	 */
	public void printGraph(){
		for (String key : graph.getVertices().keySet()){
			Vertex tmpVertex = graph.getVertex(key);
			
			System.out.println("Vertex: " + key + "\t earliest: " + tmpVertex.getEarliestTime() 
					+ "\t last: " + tmpVertex.getLastTime()  );
			System.out.println("has edges: ");
			for (Edge e : tmpVertex.getOutgoingEdges()){
				System.out.println("edge to: " + e.getDestination().getName() + " with weight: " + e.getWeight());
			}
			System.out.println();
		}
	}

	public void clearGraph(){
		graph.getVertices().clear();
	}
	
}
